#include "../tools.h"

// next[j] = k
// 0,...,k-2,k-1,...,j-k,...,j-2,j-1
// j 前面 k 个元素子串 == k 前面的 k 个元素子串
void get_next(vector<int>& next, string pattern){
    int j = 0, k = -1; // k 后缀匹配的字符串前缀 k = -1 表示没有前缀匹配
    next[0] = -1;
    while(j < pattern.size() - 1){ // 因为内部先 ++ 再插入值
        if(k == -1 || pattern[k] == pattern[j]){ // 确定了 k 的值，写到 next 数组里
            ++j;
            ++k; // k 是索引，
            next[j] = k;
        }
        else k = next[k]; // 继续向前查找
    }
}

int KMP(string str, string pattern){
    vector<int> next(pattern.size());
    get_next(next, pattern);
    int i = 0, j = 0;
    int size_str = str.size();
    int size_ptn = pattern.size();
    while(i < size_str && j < size_ptn){ // j 可能为 -1，所以必须将无符号长度转为 int 使用
        if(j == -1 || str[i] == pattern[j]){
            ++i;
            ++j;
        }
        else j = next[j];
    }

    if(j == pattern.size()) return i - pattern.size();
    else return -1;
}


int main(int argc, char const *argv[])
{
    string pattern = "ABCDABD";
    string str = "BBC ABCDAB ABCDABCDABDE";

    vector<int> next(pattern.size());
    get_next(next, pattern);
    show(next);

    int res = KMP(str, pattern);
    cout << res << endl;
    cout << str[res] << endl;
    cout << str.substr(res, str.size() - res) << endl;

    return 0;
}
